class FLIST{T} < $ARR{T}

****

Array-based lists of elements of type T. These are extensible stacks based on amortized doubling. They may often be used as replacements for linked lists. Like linked lists (which are widely used as containers in languages like Lisp), they serve as general container objects for holding collections of other objects. They are often a more efficient abstraction, however, because less allocation and deallocation must occur, because they keep successive elements in successive memory locations, because they don't require storage for the links in a linked list, and they support efficient access by array index. Linked lists also support insertion and deletion into the middle of the list. The set operations `union', `intersection', `difference', and `sym_difference' and the searching operation `index_of' are implemented by brute force search. If extensive use is made of these operations, one should consider the use of other data structures such as FSET{T}.

---

Ancestors

$ARR{_}	$RO_ARR{_}	$CONTAINER{_}	$ELT{_}
$ELT	AREF{_}

Descendants

FSTR

---

Public

Features

aget(ind:INT):T

****	The element of self with index `ind'. Self may not be void.

append(l:SAME):SAME

****	Append `l' to the end of self and return the result. Self may be void. `l' mustn't equal self unless void. Modified(ben) - hopefully much more efficient - no iters

array:ARRAY{T}

****	An array containing the elements of self. Void if self is void.

aset(ind:INT,val:T)

****	Set the element of self with index `ind' to `val'. Self may not be void.

clear

****	Clear the list. Self may be void. Clear array elements so they won't be referenced any more (and may become garbage).

concat(l:SAME):SAME

****	Append 'l' destructively. 'l' mustn't equal self unless void. Modified (ben) - hopefully more efficient - no iters, single alloc

contains(e: T): BOOL

copy:SAME

****	A copy of self. Modified (ben) - ask Claudio

create(a: ARRAY{T}): SAME

****	Create a new FLIST from the elements in the array "a" Useful for using the array shorthand for specifying the elements

create(n:INT):SAME

****	A new empty FLIST capable of storing `n' elements without extra space allocation.

create:SAME

create_empty_sized(n: INT): SAME

****	Create an flist with n elements that are set to elt_nil

create_from(a: $ELT{T}): SAME

****	Create from any container

delete(ind:INT)

****	Delete the element with index `ind' and move the last element in its place. Self may not be void.

delete(ind: INT): SAME

delete_elt(e: T)

****	Delete first occurance of element e from the list. Consider using FSET.

delete_elt(e: T): SAME

delete_elt_ordered(e: T)

****	Similar to delete_ord, but for the element "e"

delete_elt_ordered(e: T): SAME

delete_ordered(ind: INT)

****	Delete the element with index `ind' and move up all other elements (thus preseving order). More expensive than 'delete'. Self may not be void.

delete_ordered(ind: INT): SAME

difference(l:SAME):SAME

****	A new list containing the elements of self not in `l'. Doesn't modify self or `l'. Consider FSET{T} for better performance. Self may be void.

elt_eq(e1,e2:ETP):BOOL

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_lt(e1,e2:ETP):BOOL

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_nil: ETP

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

elt_str(e: T,i: INT): STR

equals(l: $RO_ARR{T}): BOOL

****	Return true if the elemetns of "l" are the same as the elements of self

fill(e: T)

has(e:T):BOOL

****	True if `e' is contained in self.

has_ind(i: INT): BOOL

index_of(e:T):INT

****	The list index of `e'. -1 if the list is void or the element is not present (not fast). Consider using FSET{T}.

inds: ARRAY{INT}

insert_after(ind:INT, val:T): SAME

****	Insert the value "val" after the index "ind". push all later elements upwards.

insert_all_after(ind:INT, val:$CONTAINER{T}):SAME

insert_all_before(ind:INT, val:$CONTAINER{T}) :SAME

insert_before(ind:INT, val:T): SAME

****	Insert val just before index "ind"

intersect(l:SAME):SAME

****	A new list containing the elements in both self and `l'. Doesn't modify self or `l'. Consider FSET{T} for better performance. Self may be void.

is_elt_nil(e:ETP):BOOL

is_empty:BOOL

****	True if the list is empty or void.

pop:T

****	Return the top element and shrink the list. Void if the list is empty or void.

push(e:T):SAME

****	Add a new element to the end of the list and return the list. If self is void, create a new list. Usage: `l:=l.push(e)'.

push_if_new(e:T):SAME

****	Push `e' if it is not already present in the list. Self may be void. Usage is: `l:=l.push_if_new(e)'. Consider using FSET{T}.

reset

****	Semantically identical to clear, but don't reset array values (space may not be freed). Useful for quickly emptying the list when you know it won't matter.

size:INT

****	The current size. Self may be void.

str: STR

****	Prints out a string version of the flist of the components that are under $STR

sublist(beg,num:INT):SAME

****	A new list with `num' entries copied from self starting at `beg'. Self may not be void.

sym_difference(l:SAME):SAME

****	A new list containing the elements in self or `l' but not both. Doesn't modify self or `l'. Consider FSET{T} for better performance. Self may be void.

to_reverse

****	Reverse the order of the elements in self. Self may be void.

top:T

****	The value of the top of the list. Void if the list is empty or void.

union(l:SAME):SAME

****	A new list containing the elements in self unioned with those in `l'. Doesn't modify self or `l'. Self may be void. Consider using FSET{T} for better performance.

valid_after_ind(i: INT): BOOL

valid_before_ind(i:INT): BOOL

Iters

elt!(once beg:INT):T

****	Yield the elements of self starting at `beg'. Don't insert elements while calling this. Modified (ben) - Looked at fast version - does not seem to be optimized out. Must ask Claudio about this

elt!(once beg,once num:INT):T

****	Yield `num' successive elements starting at index `beg'. Don't insert elements while calling this.

elt!(once beg,once num,once step:INT):T

****	Yield `num' elements starting at `beg' stepping by `step'.

elt!:T

****	Yield the elements of self in order. Self may be void. Don't insert elements while calling this. Modified (ben) - must ask Claudio

ind!:INT

set!(e: T)

---

Private

aclear

****	Set each element of self to nil. Built-in.

acopy(src:SAME)

****	Copy as many elements from `src' to self as will fit. Built-in.

acopy(beg:INT, src:SAME)

****	Copy as many elements from `src' to self as will fit when starting at index `beg' of self.

acopy(beg,num:INT, src:SAME)

****	Copy `num' elements from `src' to self starting at index `beg' of self.

acopy(beg,num,srcbeg:INT, src:SAME)

****	Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in.

aelt!(once beg:INT):T

****	Yield each element of self starting at `beg'. Built-in.

aelt!(once beg,once num:INT):T

****	Yield `num' successive elements of self starting at index `beg'. Built-in.

aelt!(once beg,once num,once step:INT):T

****	Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in.

aelt!:T

****	Yield each element of self in order. Built-in.

aind!:INT

****	Yield the indices of self in order.

aget(ind:INT):T

****	The element of self with index `ind'. Built-in.

aset(ind:INT, val:T)

****	Set the element of self with index `ind' to `val'. Built-in.

aset!(val:T)

****	Set successive elements of self to the values `val'. Built-in.

aset!(once beg:INT,val:T)

****	Set successive elements of self starting at `beg' to the values `val'.

aset!(once beg,once num:INT,val:T)

****	Set `num' successive elements of self starting at `beg' to the values `val'.

aset!(once beg,once num,once step:INT, val:T)

****	Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero.

asize:INT

****	The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in.

expand_to_size(new_size: INT): SAME

****	Expand space so that the result has space for "new_size" elements. Then set the location to new_size, indicating that it is filled After this is done, the resulting array will be of size = new_size and will have all the old elements of "self" copied over and the remaining elements (if any) void

is_legal_aelts_arg( beg, num, step:INT) :BOOL

****	True if the arguments are legal values for `aelts'.

is_legal_elts_arg(beg,num,step:INT):BOOL

****	True if the arguments are legal values for `elts'.

attr loc:INT;

****	The index to insert the next element.

attr loc:INT;

****	The index to insert the next element.

push_downward(from_ind: INT, by: INT)

****	Push all the elements from index "from_ind" downward by "ind" spots. The last elements are pushed off the end

---